By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 30, Issue 6, pp. 1739-2096

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Approximation Algorithms for Curvature-Constrained Shortest Paths

Pankaj K. Agarwal and Hongyan Wang

pp. 1739-1772

BibTeX  Abstract Full Text:  PDF

On Bipartite Drawings and the Linear Arrangement Problem

Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, and Imrich Vrto

pp. 1773-1789

BibTeX  Abstract Full Text:  PDF

Edge-Disjoint Paths in Expander Graphs

Alan M. Frieze

pp. 1790-1801

BibTeX  Abstract Full Text:  PDF

Efficient Dynamic Traitor Tracing

Omer Berkman, Michal Parnas, and Jirí Sgall

pp. 1802-1828

BibTeX  Abstract Full Text:  PDF

Quantum Entanglement and Communication Complexity

Harry Buhrman, Richard Cleve, and Wim van Dam

pp. 1829-1841

BibTeX  Abstract Full Text:  PDF

Regular Languages are Testable with a Constant Number of Queries

Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy

pp. 1842-1862

BibTeX  Abstract Full Text:  PDF

The Approximability of Constraint Satisfaction Problems

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson

pp. 1863-1920

BibTeX  Abstract Full Text:  PDF

Dual-Issue Scheduling for Binary Trees with Spills and Pipelined Loads

Waleed M. Meleis

pp. 1921-1941

BibTeX  Abstract Full Text:  PDF

A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application

Tao Jiang, Paul Kearney, and Ming Li

pp. 1942-1961

BibTeX  Abstract Full Text:  PDF

An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum, and Michael Mitzenmacher

pp. 1962-1975

BibTeX  Abstract Full Text:  PDF

Optimal Simulations between Unary Automata

Carlo Mereghetti and Giovanni Pighizzini

pp. 1976-1992

BibTeX  Abstract Full Text:  PDF

An Approximation Algorithm for Feedback Vertex Sets in Tournaments

Mao-cheng Cai, Xiaotie Deng, and Wenan Zang

pp. 1993-2007

BibTeX  Abstract Full Text:  PDF

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant

Daniele Micciancio

pp. 2008-2035

BibTeX  Abstract Full Text:  PDF

Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph

Endre Boros, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino

pp. 2036-2050

BibTeX  Abstract Full Text:  PDF

A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria

Aravind Srinivasan and Chung-Piaw Teo

pp. 2051-2068

BibTeX  Abstract Full Text:  PDF

Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms

Chengbin Chu and Rémy La

pp. 2069-2083

BibTeX  Abstract Full Text:  PDF

First-Order Specifications of Programmable Data Types

Grazyna Mirkowska, Andrzej Salwicki, Marian Srebrny, and Andrzej Tarlecki

pp. 2084-2096

BibTeX  Abstract Full Text:  PDF